有序数组链表转换成平衡二叉树
Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
给出一个排好序的数组，将它转换成二叉平衡树。对于一棵二叉搜索树，进行中序遍历，就得到了一个有序的数组。实际上这是一个中序遍历的逆过程。
首先找到数组的重点，得到数组的中点，作为根节点1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return BuildTree(nums, 0, nums.size()-1);
}
TreeNode *BuildTree(vector<int> &num, int start, int end){
if(start>end) return NULL;
if(start == end) return new TreeNode(num[start]);
int mid = (start+end)/2;
TreeNode *node = new TreeNode(num[mid]);
node->left = BuildTree(num, start, mid-1);
node->right = BuildTree(num, mid+1, end);
return node;
}
};
Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
(1)常规的做法是将上面的链表保存到数组中，从而利用上面的结果，时间复杂度为O(n),空间复杂度为O(n); (2)模仿数组的方法，首先找到链表的中点，在递归调用。T(n) = 2T(n/2) + O(n),这样会花费$O(nlogn)$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
if(!head) return NULL;
if(!head->next) return new TreeNode(head->val);
ListNode *prev = head;
ListNode *slow = head, *fast = head;
//找中点，分裂成两个链表
while(fast && fast->next){
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
TreeNode *root = new TreeNode(slow->val);
prev->next = NULL;
root->left = sortedListToBST(head);
root->right = sortedListToBST(slow->next);
return root;
}
/*ListNode* findMid(ListNode *h, ListNode *p){
if(!h || !h->next)
return h;
ListNode *slow = h, *fast = h;
p = h;
while(!fast->next && !fast->next->next){
p = slow;
slow = slow->next;
fast = fast->next->next;
}
return slow;
}*/
};
(3)最完美的方案:在这个方案中，利用递归的性质，来找到给出的以head为头结点的中点1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
ListNode *h = head;
int len = 0;
while(h){
len++;
h = h->next;
}
return convert(head, 0, len -1);
}
private:
TreeNode *convert(ListNode *&head, int start, int end) {
//注意这里递归的终止条件，这个很类似归并排序
if(start>end) return NULL;
int mid = start + (end-start)/2;
TreeNode *leftChild = convert(head, start, mid-1);
//这两行是这个程序的精华，
TreeNode *root = new TreeNode(head->val);
head = head->next;
TreeNode *rightChild = convert(head, mid+1, end);
root->left = leftChild;
root->right = rightChild;
return root;
}
};
现对上面的递归执行的过程进行分析,假设链表为1->2->3->4->5->6
求得中点是3，分成两半。
1 2 3 4 5 6(中点为3)
/ \
/ \
/ \
1 2(中点为1) 3 4 5（中点为4）
/\ /\
/ \ / \
/ \ / \
NULL 2 3 5
递归执行时执行到上面的NULL处，返回到中点1，构建节点1，此后，head后移一个单位，到达节点2(执行到rightchild处)，依次递归调用，执行到最后，head移动到中点，此时递归返回到根节点，
需要注意的是:由于要改变head的值，故要将head的地址传进去，这里用的是引用
参阅:
http://www.cnblogs.com/yuzhangcmu/p/4392084.html
http://www.cnblogs.com/feiling/p/3267917.html
http://bangbingsyb.blogspot.com/2014/11/leetcode-convert-sorted-list-to-binary.html